﻿#include <iostream>

#define P_RETURN_0 0.32f

/**
 * 以(P_RETURN_0)概率返回0，(1-P_RETURN_0)概率返回1
 */
static int returnZeroOrOneByP()
{
	auto rd = rand() % 100;
	if (rd <= 100 * P_RETURN_0)
	{
		return 0;
	}

	return 1;
}

/**
 * 等概率返回0或1
 */
static int returnZeroOrOneBy50Percent()
{
	int res;
	do 
	{
		res = (returnZeroOrOneByP() << 1) + returnZeroOrOneByP();
	} while (res == 0 || res == 0b11);

	return res == 0b01 ? 0 : 1;
}

/**
 * 等概率返回从low到high的一个数字，包括边界
 */
static int returnNumberBetweenAAndB(int low, int high)
{
	int offset = high - low;
	auto rd = rand() % (offset + 1);
	return low + rd;
}

/**
 * 等概率返回0或1, 使用returnNumberBetweenAAndB函数
 */
static int returnZeroOrOneByAAndB(int a, int b)
{
	int rd = returnNumberBetweenAAndB(a, b);
	if ((b - a + 1) % 2 == 0)
	{
		return (rd - a) % 2 == 0 ? 0 : 1;
	}

	while (rd == b)
	{
		rd = returnNumberBetweenAAndB(a, b);
	}

	return (rd - a) % 2 == 0 ? 0 : 1;
}

/**
 * 等概率返回从c到d的一个数字，包括边界
 * 需要使用returnNumberBetweenAAndB函数
 */
static int returnNumberBetweenCAndDByAAndB(int a, int b, int c, int d)
{
	if (d - c == b - a)
	{
		int rd = returnNumberBetweenAAndB(a, b);
		return c + rd - a;
	}

	unsigned n = 0x80000000;
	while ((n & (d - c)) == 0)
	{
		n >>= 1;
	}

	int mostF = (n << 1) - 1;
	int one;
	int num;
	bool canBreak;
	do 
	{
		one = 1;
		num = 0;
		while ((one & mostF) > 0)
		{
			num = (num << 1) + returnZeroOrOneByAAndB(a, b);
			one <<= 1;
		}

	} while (num > d - c);

	return c + num;
}

/**
 * 给定一个函数f，可以1~5的数字等概率返回一个。请加工出1~7的数字等概率返回一个的函数g。
 * 推广: 给定一个函数f，可以a~b的数字等概率返回一个。请加工出c~d的数字等概率返回一个的函数g。
 * 给定一个函数f，以p概率返回0，以1-p概率返回1。请加工出等概率返回0和1的函数g。
 */
int main_EqualProbabilityFunction()
{
	srand((unsigned)time(nullptr));
	int oneCount = 0;
	int zeroCount = 0;
	//for (int i = 0; i < 1000; i++)
	//{
	//	returnZeroOrOneByP() == 1 ? ++oneCount : ++zeroCount;
	//}

	//printf("one:%d, zero:%d\n", oneCount, zeroCount);

	oneCount = 0;
	zeroCount = 0;
	for (int i = 0; i < 1000; i++)
	{
		//returnZeroOrOneByAAndB(1, 9) == 1 ? ++oneCount : ++zeroCount;
	}

	//printf("one:%d, zero:%d\n", oneCount, zeroCount);

	for (int i = 0; i < 1000; i++)
	{
		//printf("%d->%d\n", i, returnNumberBetweenCAndDByAAndB(1,4,6,10));
	}

	return 1;
}